import time

def fibonacci_recursive(n):
    """递归实现（低效版本）"""
    if n <= 1:
        return n
    return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

def fibonacci_dp(n):
    """动态规划实现（优化版本）"""
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a + b
    return b

def compare_performance(n):
    """比较两种实现的性能"""
    print(f"\n计算 fibonacci({n}) 的性能对比：")
    
    # 测试递归版本
    start_time = time.time()
    result_recursive = fibonacci_recursive(n)
    end_time = time.time()
    time_recursive = end_time - start_time
    print(f"递归版本结果: {result_recursive}")
    print(f"递归版本耗时: {time_recursive:.4f} 秒")
    
    # 测试动态规划版本
    start_time = time.time()
    result_dp = fibonacci_dp(n)
    end_time = time.time()
    time_dp = end_time - start_time
    print(f"动态规划版本结果: {result_dp}")
    print(f"动态规划版本耗时: {time_dp:.4f} 秒")
    
    # 计算性能提升
    if time_recursive > 0 and time_dp > 0:
        speedup = time_recursive / time_dp
        print(f"\n性能提升: {speedup:.2f} 倍")

if __name__ == "__main__":
    # 测试较小的数
    print("测试较小的数 (n=15):")
    compare_performance(15)
    
    # 测试较大的数
    print("\n测试较大的数 (n=35):")
    compare_performance(35)
